1. Field of the Invention
The present invention relates to capacity allocation in a telecommunications network, and, more particularly, to allocation of working and restoration capacity of links of the network.
2. Description of the Related Art
In an interconnected communication network, users establish connections between a source node and a destination node with a stream of data that is transferred through the network over a network path. The data of one or more connections constitutes traffic over the network. Optical networks are typically characterized by a set of optical switches (i.e., nodes) connected via optical links. Packet networks (which may be implemented using optical networks) are typically characterized by routers (also considered nodes) interconnected by electrical or optical links. A network path for a connection between a given source-destination (node) pair is defined by a set of nodes (the source and destination node pair and any intermediate nodes) interconnected by a set of links coupled to the nodes carrying the data stream, or flow, of the connection. Each node and each link has a capacity corresponding to the traffic it may carry, and “capacity” may be a general term describing bandwidth, effective bandwidth, link quality, or similar link transmission characteristic.
Dynamic provisioning of bandwidth-guaranteed paths with fast restoration capability is an important network service feature for many networks, such as Multi-Protocol Label Switched (MPLS) networks and optical mesh networks. In optical networks, fast restoration is a major requirement since optical transport networks carry a variety of traffic types each with different, stringent reliability requirements. Similar fast restoration capabilities may be used in MPLS networks in order to provide the needed reliability for services such as packetized voice, critical virtual private network (VPN) traffic, or other quality of service (QoS) guarantees.
A connection in a network might be protected at the path level or at the link level. For link restoration (also often referred to as local restoration or as fast restoration), each link of the connection is protected by a set of pre-provisioned detour paths that exclude the link being protected. Upon failure of the link, traffic on the failed link is switched to the detour paths. Thus, link restoration provides a local mechanism to route around a link failure. In path restoration, the primary, or working, path of the connection is protected by a “diverse” backup path from source to destination. Upon failure of any of the resources on the working path, traffic is switched to the backup path by the source node. Link restoration might typically restore service much faster than path restoration because restoration is locally activated and, unlike path restoration, failure information need not propagate back through the network to the source.
Each link of a network has a corresponding capacity to transfer data, which link capacity is typically expressed as a link characteristic such as bandwidth or effective bandwidth (a quantity that takes into account transmission requirements such as buffer and/or transmission delay, packet loss, and QoS guarantees). This link capacity may be divided into working capacity and reservation capacity through network provisioning. Working capacity is the capacity of the link reserved for connections (traffic) under normal operating conditions, while reservation capacity is the capacity of the link employed for rerouting connections when a link, path, or node failure occurs within the network. For reservation capacity, several different restoration paths may commonly share the reservation capacity of a link (termed “shared reservation capacity usage”).
Two important performance metrics that are employed to evaluate different restoration routing methods are i) low restoration latency (the time it takes to switch to restoration links/paths) and ii) low restoration overhead (the amount of restoration capacity reserved in the network as a percentage of total capacity usage). Since restoration capacity is not used under normal no-failure conditions (except possibly by low priority traffic that may be preempted), the objective of minimizing restoration capacity overhead in the network translates to higher network utilization.
A given network is said to be edge bi-connected if the removal of any single link does not disconnect the network. Hence, for any link e between nodes i and j (i.e., e=(i, j)), a path Be exists from node i to node j that does not include link e. For a first exemplary network, 50% of the capacity of every link might be reserved for working traffic, where all link capacities are equal. Then, when a link e fails, its working traffic, which is at most 50% of the link's capacity, may be rerouted on detour Be, because (i) every link on Be has 50% of its capacity reserved for restoration traffic, and (ii) all link capacities are equal. Hence, for this exemplary network, 50% of the network capacity is reserved for restoration.
For a second exemplary network, edge connectivity of the network is 3 (i.e., at least 3 links must be removed to disconnect the network, where, again, all link capacities are equal. In this case, for any link e=(i,j), two link disjoint paths Be and B′e exist from node i to node j that do not include link e. Suppose that ⅔ (≈67%) of the capacity of every link is reserved for working traffic. Then, when a link e fails, half of its working traffic, which is at most ⅓ of the link capacity, may be rerouted on detour Be, and the other half on detour B′e, since (i) every link on Be and B′e has ⅓ of its capacity reserved for restoration traffic, (ii) detours Be and B′e are link disjoint, and (iii) all link capacities are equal. Hence, for the second exemplary network, 33% of the network capacity is reserved for restoration.
As these two exemplary networks illustrate, edge connectivity of the network, the link capacities, and the required link working capacities affect the allocation of capacity reserved for restoration.